/*
 * @lc app=leetcode id=60 lang=cpp
 *
 * [60] Permutation Sequence
 */
class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> nums(n, 0);
        for (int i=0; i<n; i++) {
            nums[i] = i;
        }

        while (--k) {
            nextPermutation(nums);
        }

        string s;
        for (auto i : nums) {
            s += (i+1+'0');
        }

        return s;
    }

    void nextPermutation(vector<int>& nums) {
        int len = nums.size();
        
        for (int i = len-2; i >= 0; i--) {
            if (nums[i] < nums[i+1]) {
                int k = len-1;
                while (k > i) {
                    if (nums[i] < nums[k]) {
                        break;
                    } else {
                        k--;
                    }
                }
                swap(nums[i], nums[k]);
                reverse(nums.begin()+i+1, nums.end());
                return ;
            }
        }

        reverse(nums.begin(), nums.end());
    }
};

